/* dfs&bfs algorithm for a graph */
/* reverse a graph */
/* author:nemo(nemokingdom@gmail.com) */
/* date:Apr. 14th,2008 */

#include "graph.h"

static boolean Visited[MAXVERTEX];
static int Prev[MAXVERTEX];
int Post[MAXVERTEX]; 		/* used in shortest paths in dags:path.c */
EdgeInfo Info[MAXEDGE];	/* used in MST：path.c */

static int Clock = 0;


int locate(Graph *g, char *name)
{
   int i;
   for(i = 0; i < g->v_num; i++)
      if(strcmp(g->vtab[i].name, name) == 0)
	 return i;
   return -1;
}


/* creat a graph */
void creatGraph(Graph *g)
{
   int i,j;
   int i1,i2;
   char name[MAXLEN];
   char s1[MAXLEN],s2[MAXLEN];
   int weight;
   char *s;
   Edge *edge;
   
   Clock = 0;
   printf("v,e num:\n");
   scanf("%d%d",&g->v_num,&g->e_num);
   getchar();
   
   printf("please input the vertex's name\n");
   for(i = 0; i < g->v_num; i++){
      scanf("%s",name);
      if((s = (char *)malloc(sizeof(name))) != NULL){
	 strcpy(s,name);
	 g->vtab[i].name = s;
	 g->vtab[i].edge = NULL;
      }
      else
	 exit(-1);
   }
   printf("please input the edge relation:\n");
   for(i = 0; i < g->e_num; i++){
      scanf("%s%s%d",s1,s2,&weight);
      fflush(NULL);
      
      i1 = locate(g,s1);
      i2 = locate(g,s2);

      
      if((edge = (Edge *)malloc(sizeof(Edge))) != NULL){
	 edge->vertex = i2;
	 edge->weight = weight;
	 edge->next = g->vtab[i1].edge;
	 g->vtab[i1].edge = edge;
      }
      else
	 exit(-1);
      /* error: some error may exist here */
      Info[i].from = i1;
      Info[i].to = i2;
      Info[i].weight = weight;
   }
   return;
}

static void Previsit(Graph *g,int i)
{
   printf("%s Previsit\n",g->vtab[i].name);
   Prev[i] = Clock;
   ++Clock;
}

static void Postvisit(Graph *g,int i)
{
   printf("%s Postvisit\n",g->vtab[i].name);
   Post[i] = Clock;
   ++Clock;
}

/* part of dfs, traverse from node i to other nodes it can reach */
static void traverse(Graph *g, int i)
{
   Edge *e;
   Visited[i] = TRUE;
   Previsit(g,i);		/* do something when first visit */
   for(e = g->vtab[i].edge; e != NULL; e = e->next){
      if(Visited[e->vertex] == FALSE)
	 traverse(g,e->vertex);
   }
   Postvisit(g,i);		/* do something when last visit */
}

/* dfs algorithm */
void DFS(Graph *g)
{
   int i;
   for(i = 0; i < g->v_num; i++)
      Visited[i] = FALSE;

   for(i = 0; i < g->v_num; i++)
      if(!Visited[i])
	 traverse(g,i);
}

void initQueue(Queue *q)
{
   q->end = 0;
   q->current =0;
}

static void inject(Queue *q,int i)
{
   q->q[q->end++] = i;
   printf("inject:%d\n",q->end);
}

static int eject(Queue *q)
{
   printf("eject:%d\n",q->current);

   return q->q[q->current++];
}
boolean empty(Queue *q)
{
   return((q->current == q->end));
}

   
void BFS(Graph *g,char *start)
{
   Queue q;
   initQueue(&q);
   
   int i;
   Edge *e;
   for(i = 0; i < g->v_num; i++)
      Visited[i] = FALSE;
   i = locate(g,start);
   inject(&q,i);
   while(!empty(&q)){
      i = eject(&q);
      Visited[i] = TRUE;
      printf("%s\n",g->vtab[i].name);
      for(e = g->vtab[i].edge; e!= NULL; e = e->next)
	 if(!Visited[e->vertex])
	    inject(&q,e->vertex);
   }
}

      
/* free the allocated memory */
void Free(Graph *g)
{
   int i,j;
   Vertex *v;
   Edge *e,*next;
   for(i = 0; i < g->v_num; i++){
      e = g->vtab[i].edge;
      free(g->vtab[i].name);
      for(; e != NULL; e = next){
	 next = e->next;
	 free(e);
      }
   }
}

/* reverse a directed graph */
Graph *reverse(Graph *g)
{
   int i;
   char *s;
   Graph *rg;
   Edge *e,*re;

   
   if((rg = (Graph *)malloc(sizeof(Graph))) == NULL)
      exit(-1);
   Clock = 0;
   
   rg->v_num = g->v_num;
   rg->e_num = g->e_num;
   for(i = 0; i < g->v_num; i++){
      if((s = (char *)malloc(sizeof(g->vtab[i].name))) == NULL)
	 exit(-1);
      memcpy(s,g->vtab[i].name,sizeof(g->vtab[i].name));
      rg->vtab[i].name = s;
      rg->vtab[i].edge = NULL;
   }

   for(i = 0; i < g->v_num; i++){
      for(e = g->vtab[i].edge; e != NULL; e = e->next){
	 if((re = (Edge *)malloc(sizeof(Edge))) == NULL)
	    exit(-1);
	 re->vertex = i;
	 re->next = rg->vtab[e->vertex].edge;
	 rg->vtab[e->vertex].edge = re;
      }
   }
   return rg;
}

void printorder(Graph *g)
{
   int i;
   for(i = 0; i < g->v_num; i++)
      printf("(%d,%d)\n",Prev[i],Post[i]);
   printf("\n");
}




   


